1. Field of the Invention
The present invention relates to methods and apparatus for evaluating a parametric function. More particularly, the present invention relates to methods and apparatus for the accurate rendering of higher order curves and curved surfaces represented by parametric functions on a CRT or other display.
2. Art Background
An effective way to represent curves and curved surfaces is through the use of parametric functions. Parametric functions are used in many applications areas such as seismic-geological and computer graphics.
In the computer graphics area, parametric curves and curved surfaces are common functions which are used in the computer generation of surfaces and objects on a display such as, for example, in mechanical computer aided design ("MCAD") applications. Since high speed hardware designed for rendering curved lines and curved surfaces is usually done by subdividing and rendering them on a CRT as a plurality of straight-lines or planar polygons. One method of tessellating a curve or a curved surface into line segments or planar polygons is by using the technique of forward differencing. The x, y, and z coordinates of a curve are defined by three parametric functions of the form f(t)=At.sup.3 +Bt.sup.2 +Ct+D. In the forward differencing technique, the end points of the line segments which reside on the curve are determined by calculating the values of the parametric functions in constant parametric increments. In each cycle, the value of a function can be derived incrementally from the previous cycle by three additions performed using the coefficients of the forward difference basis representing the curve (a, b, c, d). The registers representing the storage of the coefficients, i.e., the a, b, c, and d registers, are illustrated in FIG. 1. (For further information on forward differencing, see Foley and Van Dam, Fundamentals of Interactive Computer Graphics, Addison Wesley, Reading MA, pp. 531-536).
Bartels, Splines for use in Computer Graphics and Geometric Modeling describes an improved method of implementing forward differencing technique using fixed point arithmetic for rendering parametric curves.
In the Bartels method, successive "guard bits" are identified in the forward difference registers containing the values of the coefficients of the curve represented in forward difference basis. The guard bits are identified as a predetermined number of least significant bits in the forward difference register. Referring to FIG. 2, for processing curves up to 2.sup.n forward steps, n guard bits are used in the b, c, d forward difference registers successively. A forward step operation is performed with "n" guard bits truncated before adding a register to the adjacent register as illustrated by the following forward difference matrix and resulting equations. ##EQU1## Where "&gt;&gt;n" represents that a right register shift of n bits and the constant 2.sup.-n is a scale factor which indicates the shifting of the binary point to the left by n bits.
As a result, a portion of the error accumulated in the "b" register is truncated before added to the "c" register and a portion of the error accumulated in the "c" register is truncated before added to the "d" register. Thus the Bartels method provides greater precision than the traditional method as illustrated in FIG. 1 and the use of guard bits in the registers significantly increases the number of forward steps allowable in a 32 bit forward differencing technique by minimizing the error through the truncation of the guard bits.
In order to render higher order curves and surfaces, computer graphic systems typically are required to employ recursive subdivision methods which are expensive to implement in hardware because of high speed stack memory requirements and the increase in computational complexity over polygon rendering methods.
Adaptive forward differencing is an incremental technique which has been found to be useful in rendering higher order parametric curves and surfaces; see S. L. Lien, M. Shantz and V. Pratt, "Adaptive Forward Differencing for Rendering Curves and Surfaces", Computer Graphics, Vol. 21, No. 4, July 1987; M. Shantz and S. L. Chang, "Rendering Trimmed Nurbs with Adaptive Forward Differencing", Siggraph '88 proceedings, July 1988; and Shantz et al., U.S. patent application Ser. No. 047,696, filed May 8, 1987 for Method and Apparatus for Adaptive Forward Differencing in the Rendering of Curves and Surfaces. In the adaptive forward differencing technique, the parametric equation of the curve is transformed to an identical curve with a different parameterization, such that the size of the parametric increments is increased or decreased in order that the curve proceeds in substantially uniform increments such as approximately one pixel step on a display CRT. This differs from ordinary forward differencing in which the parametric increment is a constant and the step size is non uniform. Lien et. al. described a method in which the curve increment is decreased by dividing the parameter increment by two and increased by multiplying the parameter increment by two. This is implemented by multiplying the forward difference coefficients by an "Adjust Up" matrix "U" or an "Adjust Down" "D" matrix prior to multiplying the coefficients by the forward step or "forward difference" matrix which determines the next point along the curve: ##EQU2##
Klassen, "Antialiasing Cubic Splines", submitted to ACM TOG for publication, July 1988, expanded the concept of adaptive forward differencing by employing guard bits in the process. More specifically Klassen modified the adjust-up matrix and the adjust-down matrix to incorporate the usage of guard bits in the adaptive forward difference (AFD) registers (b, c, and d) and to vary the number of guard bits in the b, c, d registers after each adjustment operation such that one guard bit is added after an adjust down operation (illustrated in FIG. 3b), and one guard bit is eliminated after an adjust up operation (illustrated in FIG. 3a) giving the effect of a floating binary point in the registers. This is implemented using the adjust-up matrix Uk and adjust-down matrix Dk and the resulting equations shown below: ##EQU3##
However, in Klassen's process the binary point of the "d" register is varied. This point is critical because in the hardware implementation of AFD the d register accumulates the result of the forward step calculation which is output from the AFD circuit and is determinative of the next point along the curve. Thus, the precision of the calculation is dependent upon the number of fractional bits in the d register. This problem is particularly evident when the parametric increment is adjusted severely upward and the registers are shifted so far to the left that a minimal number of fractional bits remain. In addition, the format of the output is not constant because the format is dependent upon the number of adjust-up and adjust-down operations which have occurred. Thus the hardware which interfaces with AFD hardware is further complicated with circuitry to accommodate inputs having a floating binary point.